package com.base.dynamicprograming;

/**
 * 53. 最大子序和
 *给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
 * @author leon
 * @date 2021年11月28日 16:30
 */
public class MaxSubArray {
    /**
     * 超出内存限制
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        int max=-10000;
        for(int i=0;i<n;i++){
            for(int j = i;j<n;j++){
                if(j==i){
                    dp[i][j] = nums[j];

                }else{
                    dp[i][j] = dp[i][j-1]+nums[j];
                }
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;

    }

    /**
     * 超出实际限制
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {

        int n = nums.length;

        int max=-10000;
        for(int i=0;i<n;i++){
            int q = nums[i];
            max = Math.max(max,q);
            for(int j = i+1;j<n;j++){
                q+=nums[j];
                max = Math.max(max,q);
            }
        }
        return max;

    }

    /**
     * 动态规划：
     * 1、子问题；子问题并不一定跟父问题是同类问题
     * 2、状态转移方程 ; 状态转移方程是前面的子问题推到出后面子问题的通项公式
     * 3、无后效性; **前一个子问题定义明确，并且不依赖后一个子问题** 也就是说，一个问题求解，需要的是前一个子问题的解，不需要后一个子问题的解
     *
     * 这里的子问题是：
     * 以序号i结尾的元素的最大连续子序列和（一定是以i结尾的，也就是说nums[i]必然是在子序列和内的）
     * 由于i-1与i是相邻的，那么子问题之间的就可以相互连接起来
     *
     * 状态方程:  dp[i] = dp[i-1]+num[i]  dp[i-1]>0
     *           dp[i] = nums[i]    dp[i-1]<=0
     *
     */
    public int maxSubArray3(int[] nums) {
        int n = nums.length;
        int q = nums[0];
        int max = nums[0];
        for(int i =1;i<n;i++){
            q = Math.max(q+nums[i],nums[i]);
            // 这里的最终问题的解并不是最后一个子问题的解，而是所有子问题的解的一个最大值
            max = Math.max(max,q);
        }
        return max;
    }

    public static void main(String[] args) {
        new MaxSubArray().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
    }
}
